|
|
Řízená syntaktická analýza
Wolf, Dominik ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá rozšířenými modely bezkontextových gramatik a zkoumá možnosti jejich úpravy a využití pro deterministickou syntaktickou analýzu pomocí metod hluboké syntaktické analýzy struktur, které nejsou bezkontextové. Zavádí upravený bezkontextový model LL programovaných gramatik a hlubokého zásobníkového automatu, umožňující deterministickou syntaktickou analýzu těchto struktur.
|
|
|
Cestami řízené gramatiky
Adamec, Ondřej ; Soukup, Ondřej (oponent) ; Křivka, Zbyněk (vedoucí práce)
Tato diplomová práce se zabývá cestami řízenými gramatikami, gramatikami, které kladou omezení na cesty v derivačním stromě bezkontextové gramatiky. Cílem této diplomové práce je tvorba algoritmu pro převod mezi cestami řízenými gramatikami a stavovými gramatikami, což je jiný typ řízené gramatiky. Dalším cílem je na základě tohoto převodního algoritmu studovat vyjadřovací sílu cestami řízených gramatik. Převodní algoritmus je naimplementován v C++ a testován na sadě cestami řízených gramatik. Složitost algoritmu, jak časová, tak prostorová, je diskutována. Také nástroj pro syntaktickou analýzu cestami řízených gramatik je naimplementován. Složitost této analýzy je také diskutována.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (oponent) ; Doc. In.g Petr Sosík, Dr. (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis introduces the notion of a one-sided random context grammar as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules . A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The thesis is divided into three parts. The first part gives a motivation behind introducing one-sided random context grammars and places all the covered material into the scientific context. Then, it gives an overview of formal language theory and some of its lesser-known areas that are needed to fully grasp some of the upcoming topics. The second part forms the heart of the thesis. It formally defines one-sided random context grammars and studies them from many points of view. Generative power, relations to other types of grammars, reduction, normal forms, leftmost derivations, generalized and parsing-related versions all belong between the studied topics. The final part of this thesis closes its discussion by adding remarks regarding its coverage. More specifically, these remarks concern application perspectives, bibliography, and open problem areas.
|
|
| |
|
|
O vymazávacích pravidlech v řízených gramatikách
Zemek, Petr ; Koutný, Jiří (oponent) ; Meduna, Alexandr (vedoucí práce)
V této práci je diskutován vliv vymazávacích pravidel na generativní sílu řízených gramatik, což je velký otevřený problém teorie řízeného přepisování. Tato práce studuje možnost odstranění vymazávacích pravidel z těchto gramatik tak, že shromažďuje aktuální výsledky na toto téma a přináší novou podmínku, nazvanou k-limitované vymazávání, která zaručuje, že jsme bez vlivu na generovaný jazyk schopni odstranit všechna vymazávací pravidla z libovolné bezkontextové gramatiky řízené regulárním jazykem splňující tuto podmínku. Tento výsledek je částečným řešením výše zmíněného problému. Mimoto je prezentován nový algoritmus k odstranění vymazávacích pravidel z bezkontextových gramatik, který nepotřebuje předurčovat tzv. epsilon-neterminály (na rozdíl od standardního algoritmu používaného v učebnicích). V závěru je zhodnocen přínos těchto výsledků pro syntaktickou analýzu.
|
|
|
Paralelní syntaktická analýza
Otáhal, Jiří ; Koutný, Jiří (oponent) ; Čermák, Martin (vedoucí práce)
Diplomová práce se zabývá moderními metodami pro popis jazyků. Představuje několik řízených gramatik, přičemž podrobněji se věnuje stromem řízené gramatice. Je založena na relativně nové technice syntaktické analýzy, která využívá právě stromem řízené gramatiky. V textu je blíže popsán postup této analýzy a následně návrh, jak jí zpracovat paralelně. Daný návrh se nám podařilo implementovat a syntaktickou analýzu tím posílit z hlediska rychlosti, čímž jsme dosáhli hlavního cíle této práce.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (oponent) ; Doc. In.g Petr Sosík, Dr. (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis introduces the notion of a one-sided random context grammar as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules . A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The thesis is divided into three parts. The first part gives a motivation behind introducing one-sided random context grammars and places all the covered material into the scientific context. Then, it gives an overview of formal language theory and some of its lesser-known areas that are needed to fully grasp some of the upcoming topics. The second part forms the heart of the thesis. It formally defines one-sided random context grammars and studies them from many points of view. Generative power, relations to other types of grammars, reduction, normal forms, leftmost derivations, generalized and parsing-related versions all belong between the studied topics. The final part of this thesis closes its discussion by adding remarks regarding its coverage. More specifically, these remarks concern application perspectives, bibliography, and open problem areas.
|
|
| |
|
|
O vymazávacích pravidlech v řízených gramatikách
Zemek, Petr ; Koutný, Jiří (oponent) ; Meduna, Alexandr (vedoucí práce)
V této práci je diskutován vliv vymazávacích pravidel na generativní sílu řízených gramatik, což je velký otevřený problém teorie řízeného přepisování. Tato práce studuje možnost odstranění vymazávacích pravidel z těchto gramatik tak, že shromažďuje aktuální výsledky na toto téma a přináší novou podmínku, nazvanou k-limitované vymazávání, která zaručuje, že jsme bez vlivu na generovaný jazyk schopni odstranit všechna vymazávací pravidla z libovolné bezkontextové gramatiky řízené regulárním jazykem splňující tuto podmínku. Tento výsledek je částečným řešením výše zmíněného problému. Mimoto je prezentován nový algoritmus k odstranění vymazávacích pravidel z bezkontextových gramatik, který nepotřebuje předurčovat tzv. epsilon-neterminály (na rozdíl od standardního algoritmu používaného v učebnicích). V závěru je zhodnocen přínos těchto výsledků pro syntaktickou analýzu.
|
|
|
Řízená syntaktická analýza
Wolf, Dominik ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá rozšířenými modely bezkontextových gramatik a zkoumá možnosti jejich úpravy a využití pro deterministickou syntaktickou analýzu pomocí metod hluboké syntaktické analýzy struktur, které nejsou bezkontextové. Zavádí upravený bezkontextový model LL programovaných gramatik a hlubokého zásobníkového automatu, umožňující deterministickou syntaktickou analýzu těchto struktur.
|
host ::
RSS.